using System;
using System.Collections.Generic;
using System.Text;
using C5;

namespace CoreCalc.SheetDefinedFunctions
{
  public class TopologicalSorter
  {
    private DependencyGraph dpGraph;

    public TopologicalSorter(DependencyGraph dpGraph)
    {
      this.dpGraph = dpGraph;
    }
    
    /// <summary>
    /// Builds a list, in topological order, of all the Formula and ArrayFormula 
    /// cells that are reachable from the outputCell via the "precedent" relation.
    /// In the resulting list, each cell will be preceded by all non-constant and 
    /// non-empty cells that must be evaluated before that cell is evaluated.  
    /// </summary>
    /// <param name="outputCell">The sheet-defined function's output cell.</param>
    /// <returns></returns>
    public HashedLinkedList<FullCellAddr> Toposort(FullCellAddr outputCell)
    {
      List<FullCellAddr> allStartingCells = new List<FullCellAddr>();
      allStartingCells.Add(outputCell);
      return ToposortLogic(allStartingCells);
    }

    private HashedLinkedList<FullCellAddr> ToposortLogic(List<FullCellAddr> allStartingCells)
    {
      HashedLinkedList<FullCellAddr> sorted = new HashedLinkedList<FullCellAddr>();
      foreach (FullCellAddr start in allStartingCells)
        if (!sorted.Contains(start))
          AddNode(sorted, start);
      return sorted;
    }

    private void AddNode(C5.IList<FullCellAddr> sorted, FullCellAddr node)
    {
      HashSet<FullCellAddr> precedents;
      if (dpGraph.TryGetValue(node, out precedents))
      {
        Cell cell;
        foreach (FullCellAddr precedent in precedents)
          // By including only non-input Formula and ArrayFormula cells, we avoid that 
          // constant cells get stored in local variables.  Then input and constant
          // cells will not be in the topologically sorted list, so one needs
          // to use the raw graph to discover which cells belong to an SDF.
          if (!sorted.Contains(precedent) 
            && (precedent.TryGetCell(out cell) 
            && (cell is Formula || cell is ArrayFormula)
            && !dpGraph.inputCellSet.Contains(precedent)))
            AddNode(sorted, precedent);
      }
      sorted.InsertLast(node);
    }
  }
}